// Package day_14_two_point 8-84
// @Title day_14_two_point
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/9/7 20:01
// @Create  2021/9/7 20:01
package day_14_two_point

import (
	"fmt"
)

/**
如何枚举出所有情况？
枚举出所有柱形的上边界，作为整个矩形的上边界
然后求出左右边界:
1. 找出左边离他最近的，比他小的柱形
2. 找出右边离他最近的，比他小的柱形
------->>>>>>>> 单调栈的问题
*/

// LargestRectangleArea 组成的矩形的最大面积 使用单调栈的解法
func LargestRectangleArea(heights []int) int {
	n := len(heights)
	left, right := make([]int, n), make([]int, n)
	mono_stack := []int{}
	for i := 0; i < n; i++ {
		for len(mono_stack) > 0 && heights[mono_stack[len(mono_stack)-1]] >= heights[i] {
			mono_stack = mono_stack[:len(mono_stack)-1]
		}
		if len(mono_stack) == 0 {
			left[i] = -1
		} else {
			left[i] = mono_stack[len(mono_stack)-1]
		}
		mono_stack = append(mono_stack, i)
	}
	mono_stack = []int{}
	for i := n - 1; i >= 0; i-- {
		for len(mono_stack) > 0 && heights[mono_stack[len(mono_stack)-1]] >= heights[i] {
			mono_stack = mono_stack[:len(mono_stack)-1]
		}
		if len(mono_stack) == 0 {
			right[i] = n
		} else {
			right[i] = mono_stack[len(mono_stack)-1]
		}
		mono_stack = append(mono_stack, i)
	}
	ans := 0
	for i := 0; i < n; i++ {
		ans = max(ans, (right[i]-left[i]-1)*heights[i])
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// 暴力解决求矩形的最大面积
func LargestRectangleAreaViolence(heights []int) int {
	// 思路 固定高度，找到第一比自己小的矩形的位置 求面积
	n := len(heights)
	ans := 0
	for i := 0; i < n; i++ {
		left, right := i, i // 先记录左右边界
		for left-1 >= 0 && heights[left-1] >= heights[i] {
			left--
		}
		for right+1 < n && heights[right+1] >= heights[i] {
			right++
		}
		ans = max((right-left+1)*heights[i], ans)
		fmt.Println("------->>", left, right, i, ans)
	}
	return ans
}
